package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/linked-list-cycle-ii/
 */
public class _142_环形链表2 {
    public ListNode detectCycle(ListNode head) {
        // head.next.next == null 说明总共就两个节点，且第2个节点不是指向第一个节点
        if (head == null || head.next == null || head.next.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // 先找出slow和fast交点
        boolean hasCycle = false;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 说明有环。此时slow和fast相交
                hasCycle = true;
                break;
            }
        }

        // 此时 slow 和 fast 指向同一个节点

        if (hasCycle) {
            // fast 从头开始遍历，slow从相交节点开始走。slow走一步，fast也走一步，第一次相等的节点就是相交节点
            fast = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
        }else {
            // 单链表无环的话，就没有入环的第一个节点
            return null;
        }
        return slow;
    }
}
